@inproceedings{NanongkaiDP11,
 author = {Nanongkai, Danupon and Das Sarma, Atish and Pandurangan, Gopal},
 title = {A Tight Unconditional Lower Bound on Distributed Randomwalk Computation},
 booktitle = {Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing},
 series = {PODC '11},
 year = {2011},
 isbn = {978-1-4503-0719-2},
 location = {San Jose, California, USA},
 pages = {257--266},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/1993806.1993853},
 doi = {10.1145/1993806.1993853},
 acmid = {1993853},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {communication complexity, distributed algorithms, lower bound, randomwalk, time complexity},
} 

@inproceedings{BBF04,
    year={2004},
    isbn={978-3-540-22172-2},
    booktitle={Advanced Distributed Systems},
    volume={3061},
    series={Lecture Notes in Computer Science},
    editor={Ramos, FélixF. and Unger, Herwig and Larios, Victor},
    doi={10.1007/978-3-540-25958-9_21},
    title={Random Distributed Self-stabilizing Structures Maintenance},
    url={http://dx.doi.org/10.1007/978-3-540-25958-9_21},
    publisher={Springer Berlin Heidelberg},
    keywords={distributed systems; self-stabilization; random walks},
    author={Bernard, Thibault and Bui, Alain and Flauzac, Olivier},
    pages={231-240},
    language={English}
}



@inproceedings{ElsasserS09,
    title = "Tight bounds for the cover time of multiple random walks ",
    journal = "Theoretical Computer Science ",
    volume = "412",
    number = "24",
    pages = "2623 - 2641",
    year = "2011",
    note = "Selected Papers from 36th International Colloquium on Automata, Languages and Programming (ICALP 2009) ",
    issn = "0304-3975",
    doi = "http://dx.doi.org/10.1016/j.tcs.2010.08.010",
    url = "http://www.sciencedirect.com/science/article/pii/S0304397510004275",
    author = "Robert Elsässer and Thomas Sauerwald",
    keywords = "Random walks",
    keywords = "Markov chains",
    keywords = "Stochastic processes "
}


@inproceedings{broder,
    author={Broder, Andrei},
    booktitle={Foundations of Computer Science, 1989., 30th Annual Symposium on},
    title={Generating random spanning trees},
    year={1989},
    month={Oct},
    pages={442-447},
    doi={10.1109/SFCS.1989.63516},}

 @inproceedings{bar-ilan,
     author = {Bar-Ilan, Judit and Zernik, Dror},
     title = {Random Leaders and Random Spanning Trees},
     booktitle = {Proceedings of the 3rd International Workshop on Distributed Algorithms},
     year = {1989},
     isbn = {3-540-51687-5},
     pages = {1--12},
     numpages = {12},
     url = {http://dl.acm.org/citation.cfm?id=645946.675013},
     acmid = {675013},
     publisher = {Springer-Verlag},
     address = {London, UK, UK},
} 


@inproceedings{bar-ilan,
 author = {Bar-Ilan, Judit and Zernik, Dror},
 title = {Random Leaders and Random Spanning Trees},
 booktitle = {Proceedings of the 3rd International Workshop on Distributed Algorithms},
 year = {1989},
 isbn = {3-540-51687-5},
 pages = {1--12},
 numpages = {12},
 url = {http://dl.acm.org/citation.cfm?id=645946.675013},
 acmid = {675013},
 publisher = {Springer-Verlag},
 address = {London, UK, UK},
} 

@inproceedings{BIZ89,
 author = {Bar-Ilan, Judit and Zernik, Dror},
 title = {Random Leaders and Random Spanning Trees},
 booktitle = {Proceedings of the 3rd International Workshop on Distributed Algorithms},
 year = {1989},
 isbn = {3-540-51687-5},
 pages = {1--12},
 numpages = {12},
 url = {http://dl.acm.org/citation.cfm?id=645946.675013},
 acmid = {675013},
 publisher = {Springer-Verlag},
 address = {London, UK, UK},
} 

@article{Baala,
 author = {Baala, H. and Flauzac, O. and Gaber, J. and Bui, M. and El-Ghazawi, T.},
 title = {A Self-stabilizing Distributed Algorithm for Spanning Tree Construction in Wireless Ad Hoc Networks},
 journal = {J. Parallel Distrib. Comput.},
 issue_date = {January 2003},
 volume = {63},
 number = {1},
 month = jan,
 year = {2003},
 issn = {0743-7315},
 pages = {97--104},
 numpages = {8},
 url = {http://dx.doi.org/10.1016/S0743-7315(02)00028-X},
 doi = {10.1016/S0743-7315(02)00028-X},
 acmid = {782556},
 publisher = {Academic Press, Inc.},
 address = {Orlando, FL, USA},
 keywords = {ad hoc wireless networks, distributed algorithms, mobile agents, mobile computing, mobile networks, random spanning tree, random walks, self-stabilizing algorithms},
} 

@article{aldous,
 author = {Aldous, David J.},
 title = {The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees},
 journal = {SIAM J. Discret. Math.},
 issue_date = {November 1990},
 volume = {3},
 number = {4},
 month = nov,
 year = {1990},
 issn = {0895-4801},
 pages = {450--465},
 numpages = {16},
 url = {http://dx.doi.org/10.1137/0403039},
 doi = {10.1137/0403039},
 acmid = {87417},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
} 



 @inproceedings{aleliunas,
 author = {Aleliunas, Romas and Karp, Richard M. and Lipton, Richard J. and Lovasz, Laszlo and Rackoff, Charles},
 title = {Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems},
 booktitle = {Proceedings of the 20th Annual Symposium on Foundations of Computer Science},
 series = {SFCS '79},
 year = {1979},
 pages = {218--223},
 numpages = {6},
 url = {http://dx.doi.org/10.1109/SFCS.1979.34},
 doi = {10.1109/SFCS.1979.34},
 acmid = {1382621},
 publisher = {IEEE Computer Society},
 address = {Washington, DC, USA},
} 

 @inproceedings{goyal,
 author = {Goyal, Navin and Rademacher, Luis and Vempala, Santosh},
 title = {Expanders via Random Spanning Trees},
 booktitle = {Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms},
 series = {SODA '09},
 year = {2009},
 location = {New York, New York},
 pages = {576--585},
 numpages = {10},
 url = {http://dl.acm.org/citation.cfm?id=1496770.1496834},
 acmid = {1496834},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
} 



 @article{peleg-mst,
 author = {Garay, Juan A. and Kutten, Shay and Peleg, David},
 title = {A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees},
 journal = {SIAM J. Comput.},
 issue_date = {Feb. 1998},
 volume = {27},
 number = {1},
 month = feb,
 year = {1998},
 issn = {0097-5397},
 pages = {302--316},
 numpages = {15},
 url = {http://dx.doi.org/10.1137/S0097539794261118},
 doi = {10.1137/S0097539794261118},
 acmid = {276254},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
 keywords = {MST, distributed algorithms, min-weight spanning trees},
} 

@article{MP,
 author = {Muthukrishnan, S. and Pandurangan, Gopal},
 title = {Thresholding Random Geometric Graph Properties Motivated by Ad Hoc Sensor Networks},
 journal = {J. Comput. Syst. Sci.},
 issue_date = {November, 2010},
 volume = {76},
 number = {7},
 month = nov,
 year = {2010},
 issn = {0022-0000},
 pages = {686--696},
 numpages = {11},
 url = {http://dx.doi.org/10.1016/j.jcss.2010.01.002},
 doi = {10.1016/j.jcss.2010.01.002},
 acmid = {1809693},
 publisher = {Academic Press, Inc.},
 address = {Orlando, FL, USA},
 keywords = {Connectivity, Coverage, Local algorithm, Random geometric graphs, Sensor network models, Stretch, Thresholds},
} 



@inproceedings{kelner-madry,
 author = {Kelner, Jonathan A. and Madry, Aleksander},
 title = {Faster Generation of Random Spanning Trees},
 booktitle = {Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science},
 series = {FOCS '09},
 year = {2009},
 isbn = {978-0-7695-3850-1},
 pages = {13--21},
 numpages = {9},
 url = {http://dx.doi.org/10.1109/FOCS.2009.75},
 doi = {10.1109/FOCS.2009.75},
 acmid = {1748019},
 publisher = {IEEE Computer Society},
 address = {Washington, DC, USA},
 keywords = {spanning trees, random walks on graphs, electrical flows},
} 

@InProceedings{mihail-topaware,
  title={Towards topology aware networks},
  author={Gkantsidis, Christos and Goel, Gagan and Mihail, Milena and Saberi, Amin},
  booktitle={INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE},
  pages={2591--2595},
  year={2007},
  organization={IEEE}
}


@article{elkin-survey,
    author = "M. Elkin",
    title = "An Overview of Distributed Approximation",
    journal = {ACM SIGACT News Distributed Computing Column},
    year = {2004},
    month = {December},
    volume = {35},
    number = {4},
    pages = {40--57}
}

@incollection{dubhashi,
  title={Distributed approximation algorithms via LP-duality and randomization},
  author={Dubhashi, Devdatt and Grandoni, Fabrizio and Panconesi, Alessandro},
  journal={Handbook on Approximation Algorithms and Metaheuristics. Chapman \& Hall/CRC, Computer and Information Science Series},
  year={2007}
}


@article{khan-disc,
 author = {Khan, Maleq and Pandurangan, Gopal},
 title = {A Fast Distributed Approximation Algorithm for Minimum Spanning Trees},
 booktitle = {Proceedings of the 20th International Conference on Distributed Computing},
 series = {DISC'06},
 year = {2006},
 isbn = {3-540-44624-9, 978-3-540-44624-8},
 location = {Stockholm, Sweden},
 pages = {355--369},
 numpages = {15},
 url = {http://dx.doi.org/10.1007/11864219_25},
 doi = {10.1007/11864219_25},
 acmid = {2136076},
 publisher = {Springer-Verlag},
 address = {Berlin, Heidelberg},
 keywords = {distributed approximation algorithm, minimum spanning tree},
} 



@inproceedings{khan-podc,
 author = {Khan, Maleq and Kuhn, Fabian and Malkhi, Dahlia and Pandurangan, Gopal and Talwar, Kunal},
 title = {Efficient Distributed Approximation Algorithms via Probabilistic Tree Embeddings},
 booktitle = {Proceedings of the Twenty-seventh ACM Symposium on Principles of Distributed Computing},
 series = {PODC '08},
 year = {2008},
 isbn = {978-1-59593-989-0},
 location = {Toronto, Canada},
 pages = {263--272},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/1400751.1400787},
 doi = {10.1145/1400751.1400787},
 acmid = {1400787},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {distributed approximation, generalized steiner forests, least element lists, metric spaces, network optimization, probabilistic tree embeddings},
} 



@article{kutten-domset,
 author = {Kutten, Shay and Peleg, David},
 title = {Fast Distributed Construction of K-dominating Sets and Applications},
 booktitle = {Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing},
 series = {PODC '95},
 year = {1995},
 isbn = {0-89791-710-3},
 location = {Ottowa, Ontario, Canada},
 pages = {238--251},
 numpages = {14},
 url = {http://doi.acm.org/10.1145/224964.224990},
 doi = {10.1145/224964.224990},
 acmid = {224990},
 publisher = {ACM},
 address = {New York, NY, USA},
} 


@article{kempe,
 author = {Kempe, David and McSherry, Frank},
 title = {A Decentralized Algorithm for Spectral Analysis},
 journal = {J. Comput. Syst. Sci.},
 issue_date = {February, 2008},
 volume = {74},
 number = {1},
 month = feb,
 year = {2008},
 issn = {0022-0000},
 pages = {70--83},
 numpages = {14},
 url = {http://dx.doi.org/10.1016/j.jcss.2007.04.014},
 doi = {10.1016/j.jcss.2007.04.014},
 acmid = {1298837},
 publisher = {Academic Press, Inc.},
 address = {Orlando, FL, USA},
 keywords = {Decentralized algorithm, Eigenvectors, Large networks, Markov Chain, Spectral analysis},
} 




@inproceedings{BFFKRW,
 author = {Batu, T. and Fortnow, L. and Fischer, E. and Kumar, R. and Rubinfeld, R. and White, P.},
 title = {Testing Random Variables for Independence and Identity},
 booktitle = {Proceedings of the 42Nd IEEE Symposium on Foundations of Computer Science},
 series = {FOCS '01},
 year = {2001},
 isbn = {0-7695-1390-5},
 pages = {442--},
 url = {http://dl.acm.org/citation.cfm?id=874063.875541},
 acmid = {875541},
 publisher = {IEEE Computer Society},
 address = {Washington, DC, USA},
} 

@Article{JS89,
 author = {Jerrum, M. and Sinclair, Alistair},
 title = {Approximating the Permanent},
 journal = {SIAM J. Comput.},
 issue_date = {Dec. 1989},
 volume = {18},
 number = {6},
 month = dec,
 year = {1989},
 issn = {0097-5397},
 pages = {1149--1178},
 numpages = {30},
 url = {http://dx.doi.org/10.1137/0218077},
 doi = {10.1137/0218077},
 acmid = {76077},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
} 


@misc{LPW,
  title={{Markov chains and mixing times}},
  author={Levin, D.A. and Y.(Yuval) Peres and Elizabeth L.(Elizabeth Lee) Wilmer},
  year={2009},
  publisher={American Mathematical Society}
}

@article{Lyons,
 author = {Lyons, Russell},
 title = {Asymptotic Enumeration of Spanning Trees},
 journal = {Comb. Probab. Comput.},
 issue_date = {July 2005},
 volume = {14},
 number = {4},
 month = jul,
 year = {2005},
 issn = {0963-5483},
 pages = {491--522},
 numpages = {32},
 url = {http://dx.doi.org/10.1017/S096354830500684X},
 doi = {10.1017/S096354830500684X},
 acmid = {1074032},
 publisher = {Cambridge University Press},
 address = {New York, NY, USA},
} 


@article{Vitter85,
 author = {Vitter, Jeffrey S.},
 title = {Random Sampling with a Reservoir},
 journal = {ACM Trans. Math. Softw.},
 issue_date = {March 1985},
 volume = {11},
 number = {1},
 month = mar,
 year = {1985},
 issn = {0098-3500},
 pages = {37--57},
 numpages = {21},
 url = {http://doi.acm.org/10.1145/3147.3165},
 doi = {10.1145/3147.3165},
 acmid = {3165},
 publisher = {ACM},
 address = {New York, NY, USA},
} 

@INPROCEEDINGS{mihail,
 author = {Gkantsidis, Christos and Mihail, Milena and Saberi, Amin},
 title = {Conductance and Congestion in Power Law Graphs},
 booktitle = {Proceedings of the 2003 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems},
 series = {SIGMETRICS '03},
 year = {2003},
 isbn = {1-58113-664-1},
 location = {San Diego, CA, USA},
 pages = {148--159},
 numpages = {12},
 url = {http://doi.acm.org/10.1145/781027.781046},
 doi = {10.1145/781027.781046},
 acmid = {781046},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {conductance, congestion, expansion, internet topology, powerlaw graphs, routing},
} 


@article{dinwoodie,
ajournal = "Ann. Appl. Probab.",
author = "Dinwoodie, I. H.",
doi = "10.1214/aoap/1177004826",
journal = "The Annals of Applied Probability",
month = "02",
number = "1",
pages = "37--43",
publisher = "The Institute of Mathematical Statistics",
title = "A Probability Inequality for the Occupation Measure of a Reversible Markov Chain",
url = "http://dx.doi.org/10.1214/aoap/1177004826",
volume = "5",
year = "1995",
}


@article{elkin,
  author = {Elkin, Michael},
  biburl = {http://www.bibsonomy.org/bibtex/2811a47eeb26c24a1e159eb7421abfc16/dblp},
  date = {2007-06-02},
  description = {dblp},
  ee = {http://dx.doi.org/10.1137/S0097539704441058},
  interhash = {61929a22ae828c62b58f8d2769abe5b5},
  intrahash = {811a47eeb26c24a1e159eb7421abfc16},
  journal = {SIAM J. Comput.},
  keywords = {dblp},
  number = 2,
  pages = {433-456},
  timestamp = {2007-06-02T00:00:00.000+0200},
  title = {An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem.},
  url = {http://dblp.uni-trier.de/db/journals/siamcomp/siamcomp36.html#Elkin06},
  volume = 36,
  year = 2006
}




@inproceedings{DNP09-podc,
 author = {Das Sarma, Atish and Nanongkai, Danupon and Pandurangan, Gopal},
 title = {Fast Distributed Random Walks},
 booktitle = {Proceedings of the 28th ACM Symposium on Principles of Distributed Computing},
 series = {PODC '09},
 year = {2009},
 isbn = {978-1-60558-396-9},
 location = {Calgary, AB, Canada},
 pages = {161--170},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/1582716.1582745},
 doi = {10.1145/1582716.1582745},
 acmid = {1582745},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {distributed algorithm, metropolis-hastings sampling, random sampling, random walks},
} 

@inproceedings{DNPT10-podc,
 author = {Das Sarma, Atish and Nanongkai, Danupon and Pandurangan, Gopal and Tetali, Prasad},
 title = {Efficient Distributed Random Walks with Applications},
 booktitle = {Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing},
 series = {PODC '10},
 year = {2010},
 isbn = {978-1-60558-888-9},
 location = {Zurich, Switzerland},
 pages = {201--210},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/1835698.1835745},
 doi = {10.1145/1835698.1835745},
 acmid = {1835745},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {decentralized computation, distributed algorithms, mixing time, random sampling, random spanning tree, random walks},
} 



@book{lynch,
 author = {Lynch, Nancy A.},
 title = {Distributed Algorithms},
 year = {1996},
 isbn = {1558603484},
 publisher = {Morgan Kaufmann Publishers Inc.},
 address = {San Francisco, CA, USA},
}


@article{peleg-bound,
 author = {Peleg, David and Rubinovich, Vitaly},
 title = {A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction},
 journal = {SIAM J. Comput.},
 issue_date = {2000},
 volume = {30},
 number = {5},
 month = may,
 year = {2000},
 issn = {0097-5397},
 pages = {1427--1442},
 numpages = {16},
 url = {http://dx.doi.org/10.1137/S0097539700369740},
 doi = {10.1137/S0097539700369740},
 acmid = {586936},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
 keywords = {distributed algorithm, lower bound, minimum weight spanning tree},
} 

@inproceedings{frieze,
 author = {Cooper, Colin and Frieze, Alan and Radzik, Tomasz},
 title = {Multiple Random Walks in Random Regular Graphs},
 journal = {SIAM J. Discret. Math.},
 issue_date = {November 2009},
 volume = {23},
 number = {4},
 month = nov,
 year = {2009},
 issn = {0895-4801},
 pages = {1738--1761},
 numpages = {24},
 url = {http://dx.doi.org/10.1137/080729542},
 doi = {10.1137/080729542},
 acmid = {1898299},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
 keywords = {multiple walks, random regular graphs, random walks},
} 


@article{Gillman98,
 author = {Gillman, David},
 title = {A Chernoff Bound for Random Walks on Expander Graphs},
 journal = {SIAM J. Comput.},
 issue_date = {Aug. 1998},
 volume = {27},
 number = {4},
 month = aug,
 year = {1998},
 issn = {0097-5397},
 pages = {1203--1220},
 numpages = {18},
 url = {http://dx.doi.org/10.1137/S0097539794268765},
 doi = {10.1137/S0097539794268765},
 acmid = {284979},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
 keywords = {Ising system, Markov source, approximate counting, eigenvalue, entropy, expander, graph, large deviations, matching, partition function, random walk},
} 


@article{Jonasson98,
 author = {Jonasson, Johan},
 title = {On the Cover Time for Random Walks on Random Graphs},
 journal = {Comb. Probab. Comput.},
 issue_date = {September 1998},
 volume = {7},
 number = {3},
 month = sep,
 year = {1998},
 issn = {0963-5483},
 pages = {265--279},
 numpages = {15},
 url = {http://dx.doi.org/10.1017/S0963548398003538},
 doi = {10.1017/S0963548398003538},
 acmid = {971706},
 publisher = {Cambridge University Press},
 address = {New York, NY, USA},
} 



@inproceedings{Wilson96,
 author = {Wilson, David Bruce},
 title = {Generating Random Spanning Trees More Quickly Than the Cover Time},
 booktitle = {Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing},
 series = {STOC '96},
 year = {1996},
 isbn = {0-89791-785-5},
 location = {Philadelphia, Pennsylvania, USA},
 pages = {296--303},
 numpages = {8},
 url = {http://doi.acm.org/10.1145/237814.237880},
 doi = {10.1145/237814.237880},
 acmid = {237880},
 publisher = {ACM},
 address = {New York, NY, USA},
} 



@ARTICLE{JS00,
    author = {Johan Jonasson and Oded Schramm},
    title = {On the cover time of planar graphs},
    journal = {Elec. Comm. Probab},
    year = {2000},
    volume = {5},
    pages = {85-90}
}

@inproceedings{CooperF03,
 author = {Cooper, Colin and Frieze, Alan},
 title = {The Cover Time of Sparse Random Graphs.},
 booktitle = {Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms},
 series = {SODA '03},
 year = {2003},
 isbn = {0-89871-538-5},
 location = {Baltimore, Maryland},
 pages = {140--147},
 numpages = {8},
 url = {http://dl.acm.org/citation.cfm?id=644108.644134},
 acmid = {644134},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
} 


@inproceedings{BroderK88,
author = {Broder, Andrei Z. and Karlin, Anna R.},
  biburl = {http://www.bibsonomy.org/bibtex/2948ccf63f24e8f593dfacd51f518353d/dblp},
  booktitle = {FOCS},
  crossref = {conf/focs/FOCS29},
  ee = {http://doi.ieeecomputersociety.org/10.1109/SFCS.1988.21964},
  interhash = {61b29567fa62d998165223159dbbfa16},
  intrahash = {948ccf63f24e8f593dfacd51f518353d},
  keywords = {dblp},
  pages = {479-487},
  publisher = {IEEE Computer Society},
  timestamp = {2011-10-19T00:00:00.000+0200},
  title = {Bounds on the Cover Time (Preliminary Version)},
  url = {http://dblp.uni-trier.de/db/conf/focs/focs88.html#BroderK88},
  year = 1988
}




@inproceedings{ChandraRRST89,
 author = {Chandra, A. K. and Raghavan, P. and Ruzzo, W. L. and Smolensky, R.},
 title = {The Electrical Resistance of a Graph Captures Its Commute and Cover Times},
 booktitle = {Proceedings of the Twenty-first Annual ACM Symposium on Theory of Computing},
 series = {STOC '89},
 year = {1989},
 isbn = {0-89791-307-8},
 location = {Seattle, Washington, USA},
 pages = {574--586},
 numpages = {13},
 url = {http://doi.acm.org/10.1145/73007.73062},
 doi = {10.1145/73007.73062},
 acmid = {73062},
 publisher = {ACM},
 address = {New York, NY, USA},
} 

@article{ST08,
  title={Lower bounds for distributed markov chain problems},
  author={Sami, Rahul and Twigg, Andy},
  journal={arXiv preprint arXiv:0810.5263},
  year={2008}
}


@article{AHLP01,
  title = {Search in power-law networks},
  author = {Adamic, Lada A. and Lukose, Rajan M. and Puniyani, Amit R. and Huberman, Bernardo A.},
  journal = {Phys. Rev. E},
  volume = {64},
  issue = {4},
  pages = {046135},
  numpages = {8},
  year = {2001},
  month = {Sep},
  publisher = {American Physical Society},
  doi = {10.1103/PhysRevE.64.046135},
  url = {http://link.aps.org/doi/10.1103/PhysRevE.64.046135}
}

@inproceedings{BAS04,
 author = {Bharambe, Ashwin R. and Agrawal, Mukesh and Seshan, Srinivasan},
 title = {Mercury: Supporting Scalable Multi-attribute Range Queries},
 journal = {SIGCOMM Comput. Commun. Rev.},
 issue_date = {October 2004},
 volume = {34},
 number = {4},
 month = aug,
 year = {2004},
 issn = {0146-4833},
 pages = {353--366},
 numpages = {14},
 url = {http://doi.acm.org/10.1145/1030194.1015507},
 doi = {10.1145/1030194.1015507},
 acmid = {1015507},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {distributed hash tables, load balancing, peer-to-peer systems, random sampling, range queries},
} 



@inproceedings{LCCLS02,
 author = {Lv, Qin and Cao, Pei and Cohen, Edith and Li, Kai and Shenker, Scott},
 title = {Search and Replication in Unstructured Peer-to-peer Networks},
 booktitle = {Proceedings of the 16th International Conference on Supercomputing},
 series = {ICS '02},
 year = {2002},
 isbn = {1-58113-483-5},
 location = {New York, New York, USA},
 pages = {84--95},
 numpages = {12},
 url = {http://doi.acm.org/10.1145/514191.514206},
 doi = {10.1145/514191.514206},
 acmid = {514206},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {peer-to-peer, replication, search, unstructured},
} 


@inproceedings{GMS05,
  title={Hybrid search schemes for unstructured peer-to-peer networks},
  author={Gkantsidis, Christos and Mihail, Milena and Saberi, Amin},
  booktitle={INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE},
  volume={3},
  pages={1526--1537},
  year={2005},
  organization={IEEE}
}


@inproceedings{C05,
 author = {Cooper, Brian F.},
 title = {Quickly Routing Searches Without Having to Move Content},
 booktitle = {Proceedings of the 4th International Conference on Peer-to-Peer Systems},
 series = {IPTPS'05},
 year = {2005},
 isbn = {3-540-29068-0, 978-3-540-29068-1},
 location = {Ithaca, NY},
 pages = {163--172},
 numpages = {10},
 url = {http://dx.doi.org/10.1007/11558989_15},
 doi = {10.1007/11558989_15},
 acmid = {2138979},
 publisher = {Springer-Verlag},
 address = {Berlin, Heidelberg},
} 


@article{ZS06,
 author = {Zhong, Ming and Shen, Kai},
 title = {Random Walk Based Node Sampling in Self-organizing Networks},
 journal = {SIGOPS Oper. Syst. Rev.},
 issue_date = {July 2006},
 volume = {40},
 number = {3},
 month = jul,
 year = {2006},
 issn = {0163-5980},
 pages = {49--55},
 numpages = {7},
 url = {http://doi.acm.org/10.1145/1151374.1151386},
 doi = {10.1145/1151374.1151386},
 acmid = {1151386},
 publisher = {ACM},
 address = {New York, NY, USA},
} 

@inproceedings{KKD01,
 author = {Kempe, David and Kleinberg, Jon and Demers, Alan},
 title = {Spatial Gossip and Resource Location Protocols},
 booktitle = {Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing},
 series = {STOC '01},
 year = {2001},
 isbn = {1-58113-349-9},
 location = {Hersonissos, Greece},
 pages = {163--172},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/380752.380796},
 doi = {10.1145/380752.380796},
 acmid = {380796},
 publisher = {ACM},
 address = {New York, NY, USA},
} 


@inproceedings{K00,
 author = {Kleinberg, Jon},
 title = {The Small-world Phenomenon: An Algorithmic Perspective},
 booktitle = {Proceedings of the Thirty-second Annual ACM Symposium on Theory of Computing},
 series = {STOC '00},
 year = {2000},
 isbn = {1-58113-184-4},
 location = {Portland, Oregon, USA},
 pages = {163--170},
 numpages = {8},
 url = {http://doi.acm.org/10.1145/335305.335325},
 doi = {10.1145/335305.335325},
 acmid = {335325},
 publisher = {ACM},
 address = {New York, NY, USA},
} 

      = {http://doi.acm.org/10.1145/335305.335325}
}

@inproceedings{KR04,
 author = {Karger, David R. and Ruhl, Matthias},
 title = {Simple Efficient Load Balancing Algorithms for Peer-to-peer Systems},
 booktitle = {Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures},
 series = {SPAA '04},
 year = {2004},
 isbn = {1-58113-840-7},
 location = {Barcelona, Spain},
 pages = {36--43},
 numpages = {8},
 url = {http://doi.acm.org/10.1145/1007912.1007919},
 doi = {10.1145/1007912.1007919},
 acmid = {1007919},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {load balancing, peer-to-peer systems},
} 



@inproceedings{ZSS05,
author={Ming Zhong and Kai Shen and Seiferas, J.},
booktitle={INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE},
title={Non-uniform random membership management in peer-to-peer networks},
year={2005},
month={March},
volume={2},
pages={1151-1161 vol. 2},
keywords={computer network management;peer-to-peer computing;probability;nonuniform gossip algorithm;nonuniform random member subset;peer-to-peer networks;probability distributions;scalable random membership management algorithm;Broadcasting;Computer network management;Computer science;Delay;Intelligent networks;Load management;Network topology;Peer to peer computing;Probability distribution;Sampling methods},
doi={10.1109/INFCOM.2005.1498342},
ISSN={0743-166X},}


@article{MRRT53,
    author = {Metropolis, Nicholas   and Rosenbluth, Arianna  W.  and Rosenbluth, Marshall  N.  and Teller, Augusta  H.  and Teller, Edward  },
    citeulike-article-id = {531300},
    doi = {http://dx.doi.org/10.1063/1.1699114},
    journal = {The Journal of Chemical Physics},
    keywords = {annealing, simulated},
    number = {6},
    pages = {1087--1092},
    posted-at = {2007-07-12 12:49:56},
    priority = {2},
    publisher = {AIP},
    title = {Equation of State Calculations by Fast Computing Machines},
    url = {http://dx.doi.org/10.1063/1.1699114},
    volume = {21},
    year = {1953}
}

@article{Hastings70,
  author = {Hastings, W. K.},
  biburl = {http://www.bibsonomy.org/bibtex/2f636b3c2026f71ad7f4f6352c2175d80/mboley},
  description = {Origin of Hasting's generalization of Metropolis' algorithm.},
  doi = {10.1093/biomet/57.1.97},
  eprint = {http://biomet.oxfordjournals.org/cgi/reprint/57/1/97.pdf},
  interhash = {d8daa18a6f782f1b2e01071c453f7b4e},
  intrahash = {f636b3c2026f71ad7f4f6352c2175d80},
  journal = {Biometrika},
  keywords = {markovChains},
  number = 1,
  pages = {97-109},
  timestamp = {2009-05-22T23:03:45.000+0200},
  title = {Monte Carlo sampling methods using Markov chains and their applications},
  url = {http://biomet.oxfordjournals.org/cgi/content/abstract/57/1/97},
  volume = 57,
  year = 1970
}



@inproceedings{LawS03,
author={Law, C. and Siu, K.-Y.},
booktitle={INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies},
title={Distributed construction of random expander networks},
year={2003},
month={March},
volume={3},
pages={2133-2143 vol.3},
keywords={computer networks;distributed algorithms;network topology;protocols;Hamilton cycle;community discovery;decentralized protocol;distributed algorithm;distributed lookup service;dynamic connectivity;globally-known server;network size;node space requirement;overlay network;random expander network layered construction;Construction industry;Distributed algorithms;Eigenvalues and eigenfunctions;Graph theory;Network servers;Network topology;Peer to peer computing;Protocols;Robustness;Sampling methods},
doi={10.1109/INFCOM.2003.1209234},
ISSN={0743-166X},}

@book{chung,
  author = {Chung, F. R. K.},
  biburl = {http://www.bibsonomy.org/bibtex/295ef10b5a69a03d8507240b6cf410f8a/folke},
  interhash = {0f0fd754924d4dd54bc185bd1c71d00b},
  intrahash = {95ef10b5a69a03d8507240b6cf410f8a},
  keywords = {graph spectral theory},
  publisher = {American Mathematical Society},
  timestamp = {2009-02-05T15:34:40.000+0100},
  title = {Spectral Graph Theory},
  year = 1997
}


@book{peleg,
 author = {David Peleg},
 title = {Distributed computing: a locality-sensitive approach},
 year = {2000},
 isbn = {0-89871-464-8},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
 }


@inproceedings{PK09,
 author = {Pandurangan, Gopal and Khan, Maleq},
 chapter = {Theory of Communication Networks},
 title = {Algorithms and Theory of Computation Handbook},
 editor = {Atallah, Mikhail J. and Blanton, Marina},
 year = {2010},
 isbn = {978-1-58488-820-8},
 pages = {27--27},
 numpages = {1},
 url = {http://dl.acm.org/citation.cfm?id=1882723.1882750},
 acmid = {1882750},
 publisher = {Chapman \& Hall/CRC},
} 




@inproceedings{AKL+79,
 author = {Aleliunas, Romas and Karp, Richard M. and Lipton, Richard J. and Lovasz, Laszlo and Rackoff, Charles},
 title = {Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems},
 booktitle = {Proceedings of the 20th Annual Symposium on Foundations of Computer Science},
 series = {SFCS '79},
 year = {1979},
 pages = {218--223},
 numpages = {6},
 url = {http://dx.doi.org/10.1109/SFCS.1979.34},
 doi = {10.1109/SFCS.1979.34},
 acmid = {1382621},
 publisher = {IEEE Computer Society},
 address = {Washington, DC, USA},
} 



@article{BFG+03,
 author = {Baala, H. and Flauzac, O. and Gaber, J. and Bui, M. and El-Ghazawi, T.},
 title = {A Self-stabilizing Distributed Algorithm for Spanning Tree Construction in Wireless Ad Hoc Networks},
 journal = {J. Parallel Distrib. Comput.},
 issue_date = {January 2003},
 volume = {63},
 number = {1},
 month = jan,
 year = {2003},
 issn = {0743-7315},
 pages = {97--104},
 numpages = {8},
 url = {http://dx.doi.org/10.1016/S0743-7315(02)00028-X},
 doi = {10.1016/S0743-7315(02)00028-X},
 acmid = {782556},
 publisher = {Academic Press, Inc.},
 address = {Orlando, FL, USA},
 keywords = {ad hoc wireless networks, distributed algorithms, mobile agents, mobile computing, mobile networks, random spanning tree, random walks, self-stabilizing algorithms},
} 



@inproceedings{GoyalRV09,
 author = {Goyal, Navin and Rademacher, Luis and Vempala, Santosh},
 title = {Expanders via Random Spanning Trees},
 booktitle = {Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms},
 series = {SODA '09},
 year = {2009},
 location = {New York, New York},
 pages = {576--585},
 numpages = {10},
 url = {http://dl.acm.org/citation.cfm?id=1496770.1496834},
 acmid = {1496834},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
} 

@inproceedings{LKRG03,
 author = {Loguinov, Dmitri and Casas, Juan and Wang, Xiaoming},
 title = {Graph-theoretic Analysis of Structured Peer-to-peer Systems: Routing Distances and Fault Resilience},
 journal = {IEEE/ACM Trans. Netw.},
 issue_date = {October 2005},
 volume = {13},
 number = {5},
 month = oct,
 year = {2005},
 issn = {1063-6692},
 pages = {1107--1120},
 numpages = {14},
 url = {http://dx.doi.org/10.1109/TNET.2005.857072},
 doi = {10.1109/TNET.2005.857072},
 acmid = {1103557},
 publisher = {IEEE Press},
 address = {Piscataway, NJ, USA},
 keywords = {De Bruijn graphs, diameter-degree tradeoff, peer-to-peer networks},
} 



@inproceedings{AAKKLT,
 author = {Alon, Noga and Avin, Chen and Koucky, Michal and Kozma, Gady and Lotker, Zvi and Tuttle, Mark R.},
 title = {Many Random Walks Are Faster Than One},
 booktitle = {Proceedings of the Twentieth Annual Symposium on Parallelism in Algorithms and Architectures},
 series = {SPAA '08},
 year = {2008},
 isbn = {978-1-59593-973-9},
 location = {Munich, Germany},
 pages = {119--128},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/1378533.1378557},
 doi = {10.1145/1378533.1378557},
 acmid = {1378557},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {cover time, distributed algorithms, graph search, random walks, speed-up},
} 


@INPROCEEDINGS{costsens,
 author = {Awerbuch, Baruch and Baratz, Alan and Peleg, David},
 title = {Cost-sensitive Analysis of Communication Protocols},
 booktitle = {Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing},
 series = {PODC '90},
 year = {1990},
 isbn = {0-89791-404-X},
 location = {Quebec City, Quebec, Canada},
 pages = {177--187},
 numpages = {11},
 url = {http://doi.acm.org/10.1145/93385.93417},
 doi = {10.1145/93385.93417},
 acmid = {93417},
 publisher = {ACM},
 address = {New York, NY, USA},
} 


@article{AP92,
 author = {Awerbuch, Baruch and Peleg, David},
 title = {Routing with Polynomial Communication-space Trade-off},
 journal = {SIAM J. Discret. Math.},
 issue_date = {May 1992},
 volume = {5},
 number = {2},
 month = may,
 year = {1992},
 issn = {0895-4801},
 pages = {151--162},
 numpages = {12},
 url = {http://dx.doi.org/10.1137/0405013},
 doi = {10.1137/0405013},
 acmid = {131381},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
 keywords = {communication networks, communication-space trade-offs, graph covers, routing tables},
} 

@inproceedings{AtishGP08,
 author = {Sarma, Atish Das and Gollapudi, Sreenivas and Panigrahy, Rina},
 title = {Estimating PageRank on Graph Streams},
 journal = {J. ACM},
 issue_date = {May 2011},
 volume = {58},
 number = {3},
 month = jun,
 year = {2011},
 issn = {0004-5411},
 pages = {13:1--13:19},
 articleno = {13},
 numpages = {19},
 url = {http://doi.acm.org/10.1145/1970392.1970397},
 doi = {10.1145/1970392.1970397},
 acmid = {1970397},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {Algorithms, PageRank, graph conductance, mixing time, random walk, streaming algorithms},
} 




@book{MU-book-05,
 author = {Mitzenmacher, Michael and Upfal, Eli},
 title = {Probability and Computing: Randomized Algorithms and Probabilistic Analysis},
 year = {2005},
 isbn = {0521835402},
 publisher = {Cambridge University Press},
 address = {New York, NY, USA},
} 



@inproceedings{IJ90,
 author = {Israeli, Amos and Jalfon, Marc},
 title = {Token Management Schemes and Random Walks Yield Self-stabilizing Mutual Exclusion},
 booktitle = {Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing},
 series = {PODC '90},
 year = {1990},
 isbn = {0-89791-404-X},
 location = {Quebec City, Quebec, Canada},
 pages = {119--131},
 numpages = {13},
 url = {http://doi.acm.org/10.1145/93385.93409},
 doi = {10.1145/93385.93409},
 acmid = {93409},
 publisher = {ACM},
 address = {New York, NY, USA},
} 





@article{CTW93,
 author = {Coppersmith, Don and Tetali, Prasad and Winkler, Peter},
 title = {Collisions Among Random Walks on a Graph},
 journal = {SIAM J. Discret. Math.},
 issue_date = {Aug. 1993},
 volume = {6},
 number = {3},
 month = aug,
 year = {1993},
 issn = {0895-4801},
 pages = {363--374},
 numpages = {12},
 url = {http://dx.doi.org/10.1137/0406029},
 doi = {10.1137/0406029},
 acmid = {157659},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
 keywords = {Markov chain, collision, graph, random walk, token management},
} 

@article{DSW06,
 author = {Dolev, Shlomi and Schiller, Elad and Welch, Jennifer L.},
 title = {Random Walk for Self-Stabilizing Group Communication in Ad Hoc Networks},
 journal = {IEEE Transactions on Mobile Computing},
 issue_date = {July 2006},
 volume = {5},
 number = {7},
 month = jul,
 year = {2006},
 issn = {1536-1233},
 pages = {893--905},
 numpages = {13},
 url = {http://dx.doi.org/10.1109/TMC.2006.104},
 doi = {10.1109/TMC.2006.104},
 acmid = {1137538},
 publisher = {IEEE Educational Activities Department},
 address = {Piscataway, NJ, USA},
 keywords = {Ad hoc networks, Ad hoc networks, group communication, self-stabilization, random walk., group communication, random walk., self-stabilization},
} 


@inproceedings{DSW02,
 author = {Dolev, Shlomi and Schiller, Elad and Welch, Jennifer L.},
 title = {Random Walk for Self-Stabilizing Group Communication in Ad Hoc Networks},
 journal = {IEEE Transactions on Mobile Computing},
 issue_date = {July 2006},
 volume = {5},
 number = {7},
 month = jul,
 year = {2006},
 issn = {1536-1233},
 pages = {893--905},
 numpages = {13},
 url = {http://dx.doi.org/10.1109/TMC.2006.104},
 doi = {10.1109/TMC.2006.104},
 acmid = {1137538},
 publisher = {IEEE Educational Activities Department},
 address = {Piscataway, NJ, USA},
 keywords = {Ad hoc networks, Ad hoc networks, group communication, self-stabilization, random walk., group communication, random walk., self-stabilization},
} 

@inproceedings{DolevT10,
 author = {Dolev, Shlomi and Tzachar, Nir},
 title = {Spanders: Distributed Spanning Expanders},
 journal = {Sci. Comput. Program.},
 issue_date = {May, 2013},
 volume = {78},
 number = {5},
 month = may,
 year = {2013},
 issn = {0167-6423},
 pages = {544--555},
 numpages = {12},
 url = {http://dx.doi.org/10.1016/j.scico.2012.10.001},
 doi = {10.1016/j.scico.2012.10.001},
 acmid = {2452270},
 publisher = {Elsevier North-Holland, Inc.},
 address = {Amsterdam, The Netherlands, The Netherlands},
 keywords = {Dynamic networks, Expanders, Random walks, Self-organization, Self-stabilization},
} 




@inproceedings{Broder89,
 author = {Wilson, David Bruce},
 title = {Generating Random Spanning Trees More Quickly Than the Cover Time},
 booktitle = {Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing},
 series = {STOC '96},
 year = {1996},
 isbn = {0-89791-785-5},
 location = {Philadelphia, Pennsylvania, USA},
 pages = {296--303},
 numpages = {8},
 url = {http://doi.acm.org/10.1145/237814.237880},
 doi = {10.1145/237814.237880},
 acmid = {237880},
 publisher = {ACM},
 address = {New York, NY, USA},
} 


@inproceedings{BBSB04,
 author = {Bui, Marc and Bernard, Thibault and Sohier, Devan and Bui, Alain},
 title = {Random Walks in Distributed Computing: A Survey},
 booktitle = {Proceedings of the 4th International Conference on Innovative Internet Community Systems},
 series = {IICS'04},
 year = {2006},
 isbn = {3-540-28880-5, 978-3-540-28880-0},
 location = {Guadalajara, Mexico},
 pages = {1--14},
 numpages = {14},
 url = {http://dx.doi.org/10.1007/11553762_1},
 doi = {10.1007/11553762_1},
 acmid = {2178471},
 publisher = {Springer-Verlag},
 address = {Berlin, Heidelberg},
 keywords = {distributed algorithms, distributed system, electrical network, random walks},
} 

@inproceedings{MG07,
 author = {Morales, Ramses and Gupta, Indranil},
 title = {AVMON: Optimal and Scalable Discovery of Consistent Availability Monitoring Overlays for Distributed Systems},
 booktitle = {Proceedings of the 27th International Conference on Distributed Computing Systems},
 series = {ICDCS '07},
 year = {2007},
 isbn = {0-7695-2837-3},
 pages = {55--},
 url = {http://dx.doi.org/10.1109/ICDCS.2007.87},
 doi = {10.1109/ICDCS.2007.87},
 acmid = {1270890},
 publisher = {IEEE Computer Society},
 address = {Washington, DC, USA},
 keywords = {Churn, Availability, Monitoring, Overlay, Consistency, Scalability, Optimality.},
} 


 @article{GKM03,
 author = {Ganesh, Ayalvadi J. and Kermarrec, Anne-Marie and Massouli{\'e}, Laurent},
 title = {Peer-to-Peer Membership Management for Gossip-Based Protocols},
 journal = {IEEE Trans. Comput.},
 issue_date = {February 2003},
 volume = {52},
 number = {2},
 month = feb,
 year = {2003},
 issn = {0018-9340},
 pages = {139--149},
 numpages = {11},
 url = {http://dx.doi.org/10.1109/TC.2003.1176982},
 doi = {10.1109/TC.2003.1176982},
 acmid = {642782},
 publisher = {IEEE Computer Society},
 address = {Washington, DC, USA},
 keywords = {Scalability, reliability, peer-to-peer, gossip-based probabilistic multicast, membership, group communication, random graphs.},
} 

@inproceedings{AHKV03,
 author = {Adler, Micah and Halperin, Eran and Karp, Richard M. and Vazirani, Vijay V.},
 title = {A Stochastic Process on the Hypercube with Applications to Peer-to-peer Networks},
 booktitle = {Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing},
 series = {STOC '03},
 year = {2003},
 isbn = {1-58113-674-9},
 location = {San Diego, CA, USA},
 pages = {575--584},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/780542.780626},
 doi = {10.1145/780542.780626},
 acmid = {780626},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {coupon collector, hash table, hypercube, load balancing, peer to peer},
} 